package com.learn.algorlthm;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

/**
 * 输入链表的第一个节点，从尾到头反过来打印出每个结点的值。
 *
 */
public class Learn06 {


    class ListNode {

        private int i;
        private ListNode next;

        public int getI() {
            return i;
        }

        public void setI(int i) {
            this.i = i;
        }

        public ListNode getNext() {
            return next;
        }

        public void setNext(ListNode next) {
            this.next = next;
        }
    }

    public ListNode createListNode() {
        ListNode listNode = new ListNode();
        listNode.setI(1);

        ListNode listNode2 = new ListNode();
        listNode2.setI(2);

        ListNode listNode3 = new ListNode();
        listNode3.setI(3);

        listNode.setNext(listNode2);
        listNode2.setNext(listNode3);

        return listNode;
    }


    //1 使用栈
    public ArrayList<Integer> printListFromTailToHead1(ListNode listNode) {
        Stack<Integer> stack = new Stack<>();
        while (listNode != null) {
            stack.add(listNode.getI());
            listNode = listNode.getNext();
        }
        ArrayList<Integer> ret = new ArrayList<>();
        while (!stack.isEmpty()) {
            ret.add(stack.pop());
        }

        return ret;
    }

    //2.使用递归
    public ArrayList<Integer> printListFromTailToHead2(ListNode listNode) {
        ArrayList<Integer> ret = new ArrayList<>();
        if (listNode != null) {
            ret.addAll(printListFromTailToHead2(listNode.getNext()));
            ret.add(listNode.getI());
        }
        return ret;
    }

    //3. 使用Collctions.reverse()
    public ArrayList<Integer> printListFromTailToHead3(ListNode listNode) {
        ArrayList<Integer> ret = new ArrayList<>();
        while (listNode != null) {
            ret.add(listNode.getI());
            listNode = listNode.getNext();
        }
        Collections.reverse(ret);
        return ret;
    }

    //4. 使用头插法 (利用链表头插法为逆序的特点)
    public ArrayList<Integer> printListFromTailToHead4(ListNode listNode) {
        //头插法构建逆序链表
        ListNode head = new ListNode();
        head.setI(-1);

        while (listNode != null) {
            ListNode memo = listNode.getNext();
            listNode.setNext(head.getNext());
            head.setNext(listNode);

            listNode = memo;
        }
        //构建ArrayList
        ArrayList<Integer> ret = new ArrayList<>();
        head = head.getNext();
        while (head != null) {
            ret.add(head.getI());
            head = head.getNext();
        }
        return ret;
    }



}
